# Thompson 算法 将正规式转换为NFA
import re
from collections import OrderedDict
import numpy as np
import pandas as pd

counter = 0


class Transition:
    '''状态转移类
        State1 当前状态
        Symb 输入字符
        State2 转移后状态
    '''

    def __init__(self, State1, State2, Symb):
        self.State1 = State1
        self.State2 = State2
        self.Symb = Symb

    def __str__(self):
        return '(' + self.State1.strip() + ', ' + self.Symb + ', [' + self.State2.strip() + '])'

    def __getstate__(self):
        return [self.State1.strip(), self.Symb, self.State2.strip()]


class NFA:
    '''定义NFA类'''

    def __init__(self, States, Symbols, StartState, AcceptState, Transitions):
        self.States = States  # 状态集合
        self.Symbols = Symbols  # 输入符号
        self.StartState = StartState  # 初始状态
        self.AcceptState = AcceptState  # 终止状态
        self.Transitions = Transitions.copy()  # 状态转移


def makeStateSym(a):
    global counter
    State1 = ' q{}'.format(counter)
    counter += 1
    State2 = ' q{}'.format(counter)
    counter += 1
    tran = []
    tran.append(Transition(State1, State2, a))
    result = NFA('' + State1 + ',' + State2, '' + a, State1, State2, tran)
    # a.StartState=StartState+State1+''
    # a.AcceptStates=AcceptStates+State2+''
    # a.Symbols+=a+','
    # a.Transitions+='('+State1+','+a+',['+State2+']),'
    return result


# 交
def concat(a, b):
    '''.'''
    trans = []
    oldStates = a.States.split(',')
    newStates = ''
    removedState = a.AcceptState
    for i in range(0, len(oldStates)):
        if oldStates[i] != removedState:
            newStates += oldStates[i] + ','
    for i in range(0, len(a.Transitions)):
        if a.Transitions[i].State2 == removedState:
            a.Transitions[i].State2 = b.StartState

    newSymbols = a.Symbols + b.Symbols
    newSymbols = "".join(OrderedDict.fromkeys(newSymbols))
    result = NFA(newStates + b.States, newSymbols, a.StartState, b.AcceptState, a.Transitions + b.Transitions)
    return result


# 并
def union(a, b):
    '''|'''
    global counter
    State1 = ' q{}'.format(counter)
    counter += 1
    State2 = ' q{}'.format(counter)
    counter += 1
    trans = []
    trans.append(Transition(State1, a.StartState, ' '))
    trans.append(Transition(State1, b.StartState, ' '))
    trans.append(Transition(a.AcceptState, State2, ' '))
    trans.append(Transition(b.AcceptState, State2, ' '))
    newSymbols = a.Symbols + b.Symbols + ' '
    newSymbols = "".join(OrderedDict.fromkeys(newSymbols))
    result = NFA(State1 + ',' + State2 + ',' + a.States + ',' + b.States, newSymbols, State1, State2,
                 trans + a.Transitions + b.Transitions)
    return result


# *处理
def kleeneStar(a):
    '''*'''
    global counter
    State1 = ' q{}'.format(counter)
    counter += 1
    State2 = ' q{}'.format(counter)
    counter += 1
    trans = []
    trans.append(Transition(State1, a.StartState, ' '))
    trans.append(Transition(a.AcceptState, State2, ' '))
    trans.append(Transition(State1, State2, ' '))
    trans.append(Transition(a.AcceptState, a.StartState, ' '))
    newSymbols = a.Symbols + ' '
    newSymbols = "".join(OrderedDict.fromkeys(newSymbols))
    result = NFA(State1 + ',' + State2 + ',' + a.States, newSymbols, State1, State2, trans + a.Transitions)
    return result


# 问号标记处理
def questionMark(a):
    '''?'''
    trans = []
    trans.append(Transition(a.StartState, a.AcceptState, ' '))
    newSymbols = a.Symbols + ' '
    newSymbols = "".join(OrderedDict.fromkeys(newSymbols))
    result = NFA(a.States, newSymbols, a.StartState, a.AcceptState, trans + a.Transitions)
    return result


# 加号处理
def plus(a):
    '''+'''
    global counter
    State1 = ' q{}'.format(counter)
    counter += 1
    State2 = ' q{}'.format(counter)
    counter += 1
    trans = []
    trans.append(Transition(State1, a.StartState, ' '))
    trans.append(Transition(a.AcceptState, State2, ' '))
    trans.append(Transition(a.AcceptState, a.StartState, ' '))
    newSymbols = a.Symbols + ' '
    newSymbols = "".join(OrderedDict.fromkeys(newSymbols))
    result = NFA(State1 + ',' + State2 + ',' + a.States, newSymbols, State1, State2, trans + a.Transitions)
    return result


def infixToPostfix(expression):
    """ 中缀表达式转后缀表达式 """

    # 常量集合
    """
        附加题修改
    """
    const_c = ['PI|E']
    function_name = ['sin|cos']
    step_c = [' |\t|\n|(|)']

    operatorStack = []  # 运算符栈
    postfix = []  # 后缀
    expressionList = list(expression)  # 表达式
    concatFlag = 0  # 与拼接标记
    brackets_flag = 0  # 出现方括号

    """escape添加到下行 ()..."""
    for i in range(0, len(expressionList)):
        if expressionList[i] in 'abcdefghijklmnopqrstuvwxyz ' or expressionList[i] in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or \
                expressionList[i] in '0123456789' or (
                expressionList[i] in "();\n\t*/+-^" and i - 1 >= 0 and expressionList[i - 1] == '#'):
            postfix.append(expressionList[i])
            # 下一个如果仍然为字符则 标记为1
            if (i < (len(expressionList) - 1) and (
                    expressionList[i + 1] in 'abcdefghijklmnopqrstuvwxyz' or expressionList[
                i + 1] in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or expressionList[i + 1] in '0123456789' or expressionList[
                        i + 1] == '(' or expressionList[i+1] in "#")):
                concatFlag = 1
        # 如果为其他标记符,且保证其不是#( ,#(是表示字符(
        elif expressionList[i] == '(':
            if i - 1 >= 0 and expressionList[i - 1] == '#':
                pass
            else:
                operatorStack.append(expressionList[i])

        elif expressionList[i] == ')' and i - 1 >= 0 and expressionList[i - 1] != '#':
            # 特殊处理
            topToken = operatorStack.pop()
            while topToken != '(':
                postfix.append(topToken)
                topToken = operatorStack.pop()
            if (i < (len(expressionList) - 1) and (
                    expressionList[i + 1] in 'abcdefghijklmnopqrstuvwxyz ' or expressionList[
                i + 1] in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or expressionList[i + 1] in '0123456789')):
                concatFlag = 1

        elif expressionList[i] == '*' or expressionList[i] == '+' or expressionList[i] == '?':
            postfix.append(expressionList[i])
            if (i < (len(expressionList) - 1) and (
                    expressionList[i + 1] in 'abcdefghijklmnopqrstuvwxyz ' or expressionList[
                i + 1] in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or expressionList[i + 1] in '0123456789' or expressionList[
                        i + 1] == '(')):
                concatFlag = 1
        elif expressionList[i] == '#':
            postfix.append('#')
        else:
            operatorStack.append(expressionList[i])

        if concatFlag == 1:
            operatorStack.append('.')
        concatFlag = 0

    while not len(operatorStack) == 0:
        postfix.append(operatorStack.pop())
    # print(postfix)
    return "".join(postfix)


def operate(postfix):
    postfixList = list(postfix)
    stack = []
    for i in range(0, len(postfixList)):
        if postfixList[i] in 'abcdefghijklmnopqrstuvwxyz ' or postfixList[i] in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or \
                postfixList[i] in '0123456789' or (
                i + 1 < len(postfixList) and postfixList[i - 1] == '#' and postfixList[i] in "();\n\t*+-/^"):
            # escape添加处，上行
            r = makeStateSym(postfix[i])  # 状态
            stack.append(r)

        # 代数运算
        elif postfixList[i] == '|':
            b = stack.pop()
            a = stack.pop()
            r = union(a, b)
            stack.append(r)
        elif postfixList[i] == '*':
            a = stack.pop()
            r = kleeneStar(a)
            stack.append(r)
        elif postfixList[i] == '+':
            a = stack.pop()
            r = plus(a)
            stack.append(r)
        elif postfixList[i] == '?':
            a = stack.pop()
            r = questionMark(a)
            stack.append(r)
        elif postfixList[i] == '.':
            b = stack.pop()
            a = stack.pop()
            r = concat(a, b)
            stack.append(r)
    return r


def main(regex_str):
    file1 = open("./input.txt", 'r', encoding='utf-8')
    f = file1.read()
    file1.close()

    file2 = open("Task_2_result.txt", "w+")
    regex = regex_str
    regex = regex.replace('ε', ' ')  # 读取正规式，并用ε代替 ‘ ’
    result = ''
    r4 = operate(infixToPostfix(regex))

    result += '' + r4.States + '\n'
    result = result[1:]
    symb = ', '.join(r4.Symbols)
    result += '' + symb + '\n'
    result += '' + r4.StartState[1:] + '\n'
    result += '' + r4.AcceptState[1:] + '\n'
    for k in range(len(r4.Transitions)):
        result += Transition.__str__((r4.Transitions[k])) + ', '

    result = result[:-2]
    # print(result)
    file2.write(result)

    file2.close()

    transition_list = []
    for k in range(len(r4.Transitions)):
        transition_list.append(Transition.__getstate__(r4.Transitions[k]))

    transition_array = np.array(transition_list)
    input_set = list(set(transition_array[:, 1]))  # 输入字符集
    temp = r4.States
    temp = temp.split(',')
    for i in range(len(temp)):
        temp[i] = temp[i].strip(' ')

    if " " not in input_set:
        input_set.append(" ")
    input_set.sort()
    # print(input_set)
    NFA = np.zeros((len(temp), len(input_set)), dtype=object)
    for i in range(len(NFA)):
        for j in range(len(NFA[i])):
            NFA[i][j] = []

    for i in range(len(transition_array)):
        row_index = temp.index(transition_array[i][0])
        state_index = temp.index(transition_array[i][2])
        col_index = input_set.index(transition_array[i][1])
        NFA[row_index][col_index].append(state_index)
    start_state = temp.index(r4.StartState.strip(' '))  # 起始状态
    accept_state = temp.index(r4.AcceptState.strip(' '))  # 终止状态
    return NFA, input_set, start_state, accept_state
